//给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是
// (xi, yi) ，右上顶点是 (ai, bi) 。 
//
// 如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。 
// 
//
// 示例 1： 
//
// 
//输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
//输出：true
//解释：5 个矩形一起可以精确地覆盖一个矩形区域。 
// 
//
// 示例 2： 
//
// 
//输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
//输出：false
//解释：两个矩形之间有间隔，无法覆盖成一个矩形。 
//
// 示例 3： 
//
// 
//输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
//输出：false
//解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。 
//
// 
//
// 提示： 
//
// 
// 1 <= rectangles.length <= 2 * 10⁴ 
// rectangles[i].length == 4 
// -10⁵ <= xi, yi, ai, bi <= 10⁵ 
// 
// Related Topics数组 | 扫描线 
//
// 👍 229, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

class PerfectRectangle {
    public static void main(String[] args) {
        Solution solution = new PerfectRectangle().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://labuladong.gitee.io/algo/4/33/131/
        // 从面积和顶点2个维度来判断
        public boolean isRectangleCover(int[][] rectangles) {
            int X1 = Integer.MAX_VALUE, X2 = Integer.MIN_VALUE, Y1 = Integer.MAX_VALUE, Y2 = Integer.MIN_VALUE; // 记录期望矩形的位置
            Set<String> point = new HashSet<>();  // 记录顶点，不存在说明顶点是偶数，存在说明顶点是奇数
            int actual_size = 0;
            for (int[] rectangle : rectangles) {
                int x1 = rectangle[0], x2 = rectangle[2], y1 = rectangle[1], y2 = rectangle[3];
                X1 = Math.min(X1, x1);
                X2 = Math.max(X2, x2);
                Y1 = Math.min(Y1, y1);
                Y2 = Math.max(Y2, y2);

                // 累加小矩形的面积
                actual_size += (x2 - x1) * (y2 - y1);
                for (int[] x : new int[][]{{x1, y1}, {x1, y2}, {x2, y1}, {x2, y2}}) {
                    String val = x[0] + "," + x[1];
                    if (point.contains(val)) {
                        point.remove(val);
                    } else point.add(val);
                }
            }

            // 期望矩形的面积
            int expect_size = (X2 - X1) * (Y2 - Y1);
            // 判断面积是否相同
            if (actual_size != expect_size) return false;

            // 判断最终留下的顶点个数是否为 4
            if (point.size() != 4) return false;

            // 判断留下的 4 个顶点是否是完美矩形的顶点
            if (!point.contains(X1 + "," + Y1)) return false;
            if (!point.contains(X1 + "," + Y2)) return false;
            if (!point.contains(X2 + "," + Y1)) return false;
            if (!point.contains(X2 + "," + Y2)) return false;
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
